class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return x;
        } else if (n == -1) {
            return 1 / x;
        }
        if (n % 2 == 0) {
            double ans = myPow(x, n / 2);
            return ans * ans;
        } else {
            double ans = myPow(x, n / 2);
            if (n < 0) {
                x = 1 / x;
            }
            return ans * ans * x;
        }
    }
};